package oj;

import java.util.Random;

public class LC215 {
    Random random=new Random();
    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums,0,nums.length-1,nums.length-k);
    }
    private int quickSort(int[] nums,int i,int j,int index){
        if(i>j) return -1;
        int p=partition(nums,i,j);
        if(p==index){
            return nums[p];
        }else if(p<index){
            return quickSort(nums,p+1,j,index);

        }else{
            return quickSort(nums,i,p-1,index);
        }
    }

    /**
     * 二路快排
     * @param nums
     * @param l
     * @param r
     * @return
     */
    private int partition(int[] nums,int l,int r){
        int randomIndex=random.nextInt(r-l+1)+l;
        swap(nums,l,randomIndex);
        int value=nums[l];

        int i=l+1;
        int j=r;
        while(true){
            while(i<=r && nums[i]<value){
                i++;
            }
            while(j>=l+1 && nums[j]>value){
                j--;
            }
            if(i>j){
                break;
            }
            swap(nums,i,j);
            i++;
            j--;

        }
        swap(nums,j,l);
        return j;

    }
    private void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}

